#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int minimumSubstringsInPartition(string s)
    {
        vector<int> minPartial(s.size() + 1, INT_MAX);
        minPartial[0] = 0;
        for (int i = 0; i < s.size(); i++)
        {
            vector<int> charCount(26, 0);
            for (int j = i; j >= 0; j--)
            {
                charCount[s[j] - 'a']++;
                bool equal = true;
                int noZeroCount = 0;
                for (int l = 0; l < 26; l++)
                {
                    if (charCount[l] != 0)
                        if (noZeroCount == 0)
                            noZeroCount = charCount[l];
                        else if (noZeroCount != charCount[l])
                        {
                            equal = false;
                            break;
                        }
                }
                if (equal)
                    minPartial[i + 1] = min(minPartial[i + 1], minPartial[j] + 1);
            }
        }
        return minPartial.back();
    }
};

int main()
{
    cout << "Code3144" << endl;
    Solution s;
    string ss = "fabccddg";
    cout << s.minimumSubstringsInPartition(ss) << endl;
    return 0;
}